package com.tasks.triangle;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.logging.Logger;

/**
 * 
 PROBLEM 1
 * 
 * By starting at the top of the triangle below and moving to adjacent numbers
 * on the row below, the maximum total from top to bottom is 23.
 * 
 * 
 * 
 * 3
 * 
 * 7 4
 * 
 * 2 4 6
 * 
 * 8 5 9 3
 * 
 * 
 * 
 * That is, 3 + 7 + 4 + 9 = 23.
 * 
 * 
 * 
 * Find the maximum total from top to bottom of the triangle below:
 * 
 * 
 * 
 * 75
 * 
 * 95 64
 * 
 * 17 47 82
 * 
 * 18 35 87 10
 * 
 * 20 04 82 47 65
 * 
 * 19 01 23 75 03 34
 * 
 * 88 02 77 73 07 63 67
 * 
 * 99 65 04 28 06 16 70 92
 * 
 * 41 41 26 56 83 40 80 70 33
 * 
 * 41 48 72 33 47 32 37 16 94 29
 * 
 * 53 71 44 65 25 43 91 52 97 51 14
 * 
 * 70 11 33 28 77 73 17 78 39 68 17 57
 * 
 * 91 71 52 38 17 14 91 43 58 50 27 29 48
 * 
 * 63 66 04 68 89 53 67 30 73 16 69 87 40 31
 * 
 * 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
 **/
public final class TriangleSolver {
	private final static Logger LOGGER = Logger.getLogger(TriangleSolver.class
			.getName());

	private final Triangle triangle;

	public TriangleSolver(Triangle triangle) {
		this.triangle = triangle;
	}

	public long findMaximumTotal() {
		LOGGER.info("Calling findMaximumTotal");

		List<List<Integer>> copy = triangle.getTriangleData();

		// process the data from the bottom to the top
		for (int i = copy.size() - 1; i >= 0; i--) {
			List<Integer> layer = copy.get(i);
			for (int j = 0; j < layer.size(); j++) {
				Integer value = layer.get(j);
				Integer bestSolution = findMaximumTotal(i, j, copy);

				if (!value.equals(bestSolution)) {
					// replace the value with the best solution
					layer.set(j, bestSolution);
				}
			}
		}

		// the maximum total must be at the header of the triangle
		long total = copy.get(0).get(0);

		LOGGER.info("Calculated the total: " + total);

		return total;
	}

	public long findMaximumTotal2() {
		List<List<Integer>> copy = triangle.getTriangleData();

		int value = copy.get(0).get(0);

		return findMaximumTotal2(copy, new Child(0, 0, value));
	}

	public long findMaximumTotal2(List<List<Integer>> copy, Child current) {
		List<Child> children = getChidren(copy, current);

		long max = 0;
		if (children.isEmpty()) {
			return current.value;
		} else {
			for (Child child : children) {
				max = max < current.value + findMaximumTotal2(copy, child) ? current.value
						+ findMaximumTotal2(copy, child)
						: max;
			}

		}
		return max;
	}

	private List<Child> getChidren(List<List<Integer>> copy, Child current) {
		List<Child> result = Collections.emptyList();

		if (current.i + 1 < copy.size()) {
			result = new ArrayList<Child>();

			int adjacentCenter = copy.get(current.i + 1).get(current.j);

			result.add(new Child(current.i + 1, current.j, adjacentCenter));

			int adjacentRight = copy.get(current.i + 1).get(current.j + 1);

			result.add(new Child(current.i + 1, current.j + 1, adjacentRight));

			if (current.j > 0) {
				int adjacentLeft = copy.get(current.i + 1).get(current.j - 1);
				result.add(new Child(current.i + 1, current.j - 1, adjacentLeft));
			}
		}

		return result;
	}

	/**
	 * Find the maximum for the given element.
	 * 
	 * This method checks the adjacent nodes from the previous layer and adds
	 * the maximum total from the adjacent node to the current value.
	 * 
	 * @param layer
	 *            the layer to look for.
	 * @param position
	 *            the item position.
	 * @param data
	 *            the temporary storage with the maximum totals.
	 * @return the maximum total from the adjacent node to the current value.
	 */
	private int findMaximumTotal(int layer, int position,
			List<List<Integer>> data) {
		LOGGER.info("Calling findMaximumTotal for the layer");

		int result = data.get(layer).get(position);

		if (layer + 1 < data.size()) {
			int maxValue = 0;

			int adjacentCenter = data.get(layer + 1).get(position);

			maxValue = maxValue < adjacentCenter ? adjacentCenter : maxValue;

			int adjacentRight = data.get(layer + 1).get(position + 1);

			maxValue = maxValue < adjacentRight ? adjacentRight : maxValue;

			if (position > 0) {
				int adjacentLeft = data.get(layer + 1).get(position - 1);
				maxValue = maxValue < adjacentLeft ? adjacentLeft : maxValue;
			}

			result += maxValue;
		}

		LOGGER.info("Calculated the total for the layer: " + result);

		return result;
	}

	private static class Child {
		int i;

		int j;

		int value;

		public Child(int i, int j, int value) {
			this.i = i;
			this.j = j;
			this.value = value;
		}
	}

}
